package com.practice.dp;

import java.util.Arrays;

public class Milestone2 {
	private int N;
	private int[] map;
	private int[] sum;
	private int[] d;
	
	public int[] findMilestones(int[] dist) {
		Arrays.sort(dist);
		d = dist;
		int L = d.length;
		N = (int) (Math.sqrt(8*d.length + 1) - 1) / 2;
		
		map = new int[d[L-1] + 1];
		for (int i : d) {
			map[i]++;
		}
		
		sum = new int[N];
		sum[N-1] = d[L-1];
		
		if (!dfs(N-2, L-2)) return null;
		int[] s = new int[N];
		s[0] = sum[0];
		for (int i=1; i<N; i++) {
			s[i] = sum[i] - sum[i-1];
		}
		return s;
	}
	
	private boolean dfs(int target, int upper) {
		if (target < 0) return true;		// found answer
		int lower = (target-1) * target / 2;
		
		for (int i=upper; i>=lower; i--) {
			if (map[d[i]] == 0) continue;
			while (i>0 && d[i]==d[i-1]) i--;
			sum[target] = d[i];
			map[d[i]]--;
			if (test(target)) {
				if (dfs(target - 1, i-1)) {
					return true;
				}
				else {
					for (int j=target+1; j<N; j++) {
						map[sum[j] - sum[target]]++;
					}
				}
			}
			map[d[i]]++;
		}
		
		return false;
	}
	
	private boolean test(int target) {
		for (int i=N-1; i>target; i--) {
			int j = sum[i] - sum[target];
			map[j]--;
			if (map[j] < 0) {
				for (int k=N-1; k>=i; k--) {
					map[sum[k] - sum[target]]++;
				}
				return false;
			}
		}
		return true;
	}
}
